#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
https://www.lintcode.com/problem/house-robber/description
"""


class Solution:
    """
    @param A: An array of non-negative integers
    @return: The maximum amount of money you can rob tonight
    """
    def houseRobber(self, A):
        max_with_ele = 0
        max_without = 0

        for idx in range(len(A)):
            back_max_with_ele = max_with_ele
            max_with_ele = max_without + A[idx]
            max_without = max(max_without, back_max_with_ele)
            # print(max_with_ele, max_without)

        return max(max_with_ele, max_without)


def test():
    s = Solution()
    assert s.houseRobber([3, 8, 4]) == 8
    assert s.houseRobber([5, 2, 1, 3]) == 8

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
